<head>
    <meta charset="UTF-8">
<title>算法提高 道路和航路</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div class="sec_header">
问题描述</div>
<div class="sec_cont">
<p>农夫约翰正在针对一个新区域的牛奶配送合同进行研究。他打算分发牛奶到T个城镇（标号为1..T），这些城镇通过R条标号为（1..R）的道路和P条标号为（1..P）的航路相连。</p>
<p>每一条公路i或者航路i表示成连接城镇A<sub>i</sub>（1&lt;=A_i&lt;=T）和B<sub>i</sub>（1&lt;=B<sub>i</sub>&lt;=T）代价为C<sub>i</sub>。每一条公路，C<sub>i</sub>的范围为0&lt;=C<sub>i</sub>&lt;=10,000；由于奇怪的运营策略，每一条航路的C<sub>i</sub>可能为负的，也就是-10,000&lt;=C<sub>i</sub>&lt;=10,000。</p>
<p>每一条公路都是双向的，正向和反向的花费是一样的，都是非负的。</p>
<p>每一条航路都根据输入的A<sub>i</sub>和B<sub>i</sub>进行从A<sub>i</sub>-&gt;B<sub>i</sub>的单向通行。实际上，如果现在有一条航路是从A<sub>i</sub>到B<sub>i</sub>的话，那么意味着肯定没有通行方案从B<sub>i</sub>回到A<sub>i</sub>。</p>
<p>农夫约翰想把他那优良的牛奶从配送中心送到各个城镇，当然希望代价越小越好，你可以帮助他嘛？配送中心位于城镇S中（1<=S<=T）。</p>

</div>
<div class="sec_header">
输入格式</div>
<div class="sec_cont">
	<p>输入的第一行包含四个用空格隔开的整数T，R，P，S。</p>
	<p>接下来R行，描述公路信息，每行包含三个整数，分别表示A<sub>i</sub>，B<sub>i</sub>和C<sub>i</sub>。</p>
	<p>接下来P行，描述航路信息，每行包含三个整数，分别表示A<sub>i</sub>，B<sub>i</sub>和C<sub>i</sub>。</p>
</div>
<div class="sec_header">
输出格式</div>
<div class="sec_cont">
	输出T行，分别表示从城镇S到每个城市的最小花费，如果到不了的话输出NO PATH。
</div>
<div class="sec_header">
样例输入</div>
<div class="sec_text">
6 3 3 4<br />
1 2 5<br />
3 4 5<br />
5 6 10<br />
3 5 -100<br />
4 6 -100<br />
1 3 -10
</div>
<div class="sec_header">
样例输出</div>
<div class="sec_text">
NO PATH<br />
NO PATH<br />
5<br />
0<br />
-95<br />
-100
	</div>
<div class="sec_header">
数据规模与约定</div>
<div class="sec_cont">
<p>对于20%的数据，T&lt;=100，R&lt;=500，P&lt;=500；</p>
<p>对于30%的数据，R&lt;=1000，R&lt;=10000，P&lt;=3000；</p>
<p>对于100%的数据，1&lt;=T&lt;=25000，1&lt;=R&lt;=50000，1&lt;=P&lt;=50000。</p>
</div>
